2The Mathematics of Algorithms 算法中的

Size of a Problem Instance 实例化问题的规模

输入数据的规模的增加，只是在乘一个常数。
输入数据的规模，对电脑来说，翻几倍等同于没变，他们几乎等价。
计算机用数组（array）高效的存储一组数据，可以快速访问其中排在某一位的数据。

Rate of Growth of Functions 函数增长的速度

注意算法运行的平台，包括：电脑设备、所用语言、编程环境、后台运行的其他进程。
顺序查找的时间问题，E(n)=(n+1)/2，是 n 的一元函数
考虑当 n~无穷大时，E(n) 的近似即可，对于上面的式子，E(n) 约等于 n/2
我们说顺序查找的运算时间和问题的规模成线性函数关系，忽略掉 1/2 这个系数，只有当问题规模很大时才考虑
我们用这种方法选择更好的算法时，要记住：硬件很重要，n 不一定一直很大（第四章的快速排列快于插入排列，但 n 小时，插入排列更优。
这个函数体现了长远的趋势，决定了输入数据很大时算法的表现。可见数据量小的时候不同算法运算速度可能与数据量大时完全不同。
qsort 时 quicksort 的算法，Bentley and McIlroy 描述了快速排列算法在数据量不同时的不同优化方法。

Analysis in the Best, Average, and Worst Cases 分析最好、一般、最坏情况

不同算法在输入数据规模相同，但数据特征可能不同：有可能数据本身已经有大量元素排列好了，有可能有重复数据，有可能数据本身范围/跨度比较小
选择一个算法取决于，了解题目如何解决，理解题目数据范围潜在的可能分配，知道各种算法在数据不同时的表现。
从三种情况考虑算法的时间：最差情况，最好情况、一般情况。最差情况：尽可能阻止程序高效运行，往往最好考虑。一般情况：尽可能找到随机、普通的情况。最好情况：找到程序运行时间最短的情况。三种情况考虑后，就可以决定算法是否适合你自己的特殊情况了。
最坏情况分析，Sn 是数据量为 n 时的数据规模，t() 代表某数据规模下执行算法要的时间，那么 Twc(n) 代表了数据量为 n 时的最坏情况的执行时间（wc=worst case），那么 Twc(n) 的增长速度就代表了算法的最坏情况的时间复杂度。我们没有足够的资源计算那种情况是最坏情况，只能凭借经验判断，同时题目有可能会给出最坏情况。
平均情况分析，pr{si}是规模为 n 时，数据表现为 si 这种样子的可能性，那么 Tac(n)（平均时间）就是所有的 t(si)*pr{si}相加。此时 Tac(n) 的增长速率代表了算法一般情况的时间复杂度。
最好情况分析，很少出现但有一定参考价值。但不能通过最好情况或最坏情况判断算法的优劣。
Lower and upper bounds 上下限，假设有一个算法，当输入数据规模一直增大，他的最坏表现的时间恒小于某一函数。精确的说，当 n>n0 时，t(n)<=f(n) 恒成立，此时我们说 n0 已经足够大，我们用 O(f(n)) 表示算法的上界 (upper bound)/时间复杂度（其中写在 O 里的 f(n) 要去掉系数和常数，变成 n,n^2 之类的简单函数）。
假设有一个算法，当数据规模不断增大，他的最好表现时间恒大于某一函数。准确的说，当 n>n0 时，t(n)>f(n) 恒成立，此时我们说 n0 已经足够大，我们用Ω(f(n)) 表示算法的下界 (lower bound)。但是这样表示会丢失信息系数和常数的信息，只知道大概。
Θ(f(n))，当 O 与Ω的 f(n) 相等时，我们统一称为Θ(f(n))，英文 tight bound

Performance families

性能描述手段

我们通过输入数据的规模并进行计算，判断算法的运行时间，这主要决定了算法的优劣，第二重要的要素是算法执行消耗的内存和外存。我们用几个量准确的描述这两个要素。
Constant:O(1)

Logarithmic:O(logn)

Sublinear:O(n^d) for d<1

Linear:O(n)

Linearithmic:O(nlogn)

Quadratic:O(n^2)

Exponential:O(2^n)

注意如果分成两个子问题，那 O 取决于更大的那个。
2. 算法的表现是确定的，无论数据规模，我们认为算法的效率已经在写出来后确定了，而不取决于输入数据，也不考虑电脑硬件的问题。
3. O(logn) 猜数游戏，数在[a,b] 里，一共 n 个数。每猜一个数，它告诉你大了还是小了，直至猜中。
算法是每次取中点，这种算法最多猜 k=1+log2（n) 向下取整这么多次就一定能猜中。同时在猜第 i 次后，误差已经在在±e=2^(k-i)-1 以内。
4. 另一个 O(logn) 的算法例子，找方程 f(x) 的根，解空间长度是 n，找两个符号相反的数，然后一直找中点，看其与 0 的关系，再取区间继续对半，直到中点为 0，或满足精度要求。
5. O(n^d) for d<1 的例子，k-d tree 在多维的情况下被高效分为一系列 n 维的点。如果是一颗平衡树，顺着点的轴查找所花费的时间是 O(n^(1-1/d)），一个二维区域的话，算法的表现是 O(sqrt(n)）
6. Linear:O(n) 的例子，两个整数相加，n 代表数据位数（也可以选择 n 就是这个数，可是如果以这种增速为数据规模增速的话，就会发现 1+1 和 2+2 耗费的时间是一样的，问题描述就不清楚了）。可以看作许多数位的相加，个位数加个位数。分为 add 和 plus 两种。add：先通过%10 算出本位，再判断是否进位。plus：先判断是否进位，通过如果进位就 -10，不进位就不减，算出本位。通过不同语言下，plus 和 add 随规模的变化，说明了 O 不随设备变化而变化。（发现 add 比 plus 时间长，因为% 耗费时间多）
7. 数据规模和时间之间的系数 c 并不如时间的增长模式重要。并不是说 c 就无意义，实际上如果我们重复的加很多次，很小的 c 的不同也会导致对速度很大的影响。
8. 用 t(n) 代表数据规模是 n 时，算法所需要的时间。那么运用分治法后，算法所需要的时间变为 t(n)=2*t(n/2)+c*n。（合并问题的时间如果小于分化问题后问题时间的缩短量，那么这样做就是值得的。同理再次判断是否仍能分治。）分治 k 次后，t(n)=(2^k)*t(n/2^k)+k*c*n，当 2^k=n 时，问题已经被完全分解。用 d 表示 t(1)，那么经过彻底分治，问题的计算时间变为了 t(n)=n*d+c*n*log(n) 可以被写为 O(nlogn)
9. Quadratic:O(n^2) 例子，乘法。用小学的竖式的方法做乘法，n 代表数据位数，乘法分为两种算法，一种是 mult（带有%），一种是 times（听说有两百多行，但没有%），这两种曲线对比发现，mult 几乎是 times 时间的两倍，但这两种算法都是 O(n^2)。存在运算一对 n 位数之间的乘法，O 小于二次型的算法，这对于数据加密很有用。
10. 在读一个算法的程序时，看出它的增长类型就已经足够了，比如二次型的主要指标是嵌套循环。但是有些算法无法直截了当的分析，比如 GCD 算法（Euclid 设计）计算两个数的最大公约数。更相减损术，确定的数据规模需要的运算次数可能有很大差异。最坏情况下计算（10^k-1,1）需要外层循环 10^k-1 次。更相减损术被分为了 O(n^2) 这一类。
11. 辗转相除法 (ModGCD) 比 GCD 的算法表现更好，因为它不会在很小数和很大数之间浪费循环计算时间。但同样的，它也是 O(n^2)，并发现它在最坏情况的计算发生于两个连续的 fibonacci 数。
12. Exponential:O(2^n)，想象一个 n 位数密码，每一位是 0~9。那么可能的密码数是 10^n 个，如果硬算的话，问题的规模就是 O(10^n)。只要是大于 1 的 n 次方，我们都认为是同一种增长模式，大部分时候都是 O(2^n)。这类算法只有在 n 很小时可以使用，或者有一些算法最坏情况是 2^n，但平均情况下不是，比如解决线性规划类问题的单纯形算法 (Simplex algorithm for solving linear programming problems)
13. Asymptotic Growth 渐进增长，有更好的渐近增长的算法最终一定会快过渐近增长不好的算法，无论什么具体情况。虽然算法不同情况下的停止点不同，但何时停止可以被经验性判断。在渐进分析时，我们只考虑那个 t(n) 增长的最快，因此可以忽略许多 t(n) 里面的常数以及低次项。

Benchmark Operations 基准操作
python 可以计算 2^851，python 在相当大的程度上不受底层平台的限制，大部分平台的 java 和 c 就会导致 numeric overflow 数字溢出。
研究发现，在 python 运用** 计算时，算法是 exponentiation by squaring 算法，计算 2^x 时，运算规模是 O(n^2)。
对于问题 PI*2^x，python 的计算时间在{63，64}之间突然暴增，是因为单个内存单元不够，储存到别的单元了，时间因此增加，解释这种问题只能找基准原理